{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Students Taking Exam"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #bitmask #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #状态压缩 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxStudents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #参加考试的最大学生数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m&nbsp;* n</code>&nbsp;的矩阵 <code>seats</code>&nbsp;表示教室中的座位分布。如果座位是坏的（不可用），就用&nbsp;<code>'#'</code>&nbsp;表示；否则，用&nbsp;<code>'.'</code>&nbsp;表示。</p>\n",
    "\n",
    "<p>学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的&nbsp;<strong>最大&nbsp;</strong>学生人数。</p>\n",
    "\n",
    "<p>学生必须坐在状况良好的座位上。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/09/image.png\" style=\"height: 197px; width: 339px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>seats = [[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],\n",
    "&nbsp;             [\".\",\"#\",\"#\",\"#\",\"#\",\".\"],\n",
    "&nbsp;             [\"#\",\".\",\"#\",\"#\",\".\",\"#\"]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>seats = [[\".\",\"#\"],\n",
    "&nbsp;             [\"#\",\"#\"],\n",
    "&nbsp;             [\"#\",\".\"],\n",
    "&nbsp;             [\"#\",\"#\"],\n",
    "&nbsp;             [\".\",\"#\"]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>让所有学生坐在可用的座位上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>seats = [[\"#\",\".\",\"<strong>.</strong>\",\".\",\"#\"],\n",
    "&nbsp;             [\"<strong>.</strong>\",\"#\",\"<strong>.</strong>\",\"#\",\"<strong>.</strong>\"],\n",
    "&nbsp;             [\"<strong>.</strong>\",\".\",\"#\",\".\",\"<strong>.</strong>\"],\n",
    "&nbsp;             [\"<strong>.</strong>\",\"#\",\"<strong>.</strong>\",\"#\",\"<strong>.</strong>\"],\n",
    "&nbsp;             [\"#\",\".\",\"<strong>.</strong>\",\".\",\"#\"]]\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>让学生坐在第 1、3 和 5 列的可用座位上。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>seats</code>&nbsp;只包含字符&nbsp;<code>'.'&nbsp;和</code><code>'#'</code></li>\n",
    "\t<li><code>m ==&nbsp;seats.length</code></li>\n",
    "\t<li><code>n ==&nbsp;seats[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 8</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 8</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-students-taking-exam](https://leetcode.cn/problems/maximum-students-taking-exam/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-students-taking-exam](https://leetcode.cn/problems/maximum-students-taking-exam/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],[\".\",\"#\",\"#\",\"#\",\"#\",\".\"],[\"#\",\".\",\"#\",\"#\",\".\",\"#\"]]', '[[\".\",\"#\"],[\"#\",\"#\"],[\"#\",\".\"],[\"#\",\"#\"],[\".\",\"#\"]]', '[[\"#\",\".\",\".\",\".\",\"#\"],[\".\",\"#\",\".\",\"#\",\".\"],[\".\",\".\",\"#\",\".\",\".\"],[\".\",\"#\",\".\",\"#\",\".\"],[\"#\",\".\",\".\",\".\",\"#\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "状态压缩dp\n",
    "dp[i][j] 表示第i行的座位分布为j时，前i行可容纳最多学生人数\n",
    "'''\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0]),\n",
    "        dp = [[0]*(1 << n) for _ in range(m+1)]  # 状态数组 dp\n",
    "        # 将 # 设为 1，当遇到 . 时与运算结果为 0，表示可以坐人\n",
    "        a = [reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#'])  for i in range(m)] \n",
    "        # print(a)\n",
    "        for row in range(m)[::-1]: # 倒着遍历\n",
    "            for j in range(1 << n):\n",
    "                # j & a[row]代表该位置可以坐人，j & j<<1 and not j&j>>1 表示该位置左右没人可以坐的\n",
    "                if not j & j<<1 and not j&j>>1 and not j & a[row]:\n",
    "                    for k in range(1 << n):\n",
    "                        if not j&k<<1 and not j&k>>1: # j状态的左上和右上没有人\n",
    "                            dp[row][j] = max(dp[row][j], dp[row+1][k] + bin(j).count('1'))\n",
    "        # print(dp)\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n=len(seats),len(seats[0]),\n",
    "        dp=[[0]*(1<<n) for _ in range(m+1)]\n",
    "        a=[reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#'])  for i in range(m)]\n",
    "        for row in range(m)[::-1]:\n",
    "            for j in range(1<<n):\n",
    "                if not j&j<<1 and not j&j>>1 and not j&a[row]:\n",
    "                    for k in range(1<<n):\n",
    "                        if not j&k<<1 and not j&k>>1:\n",
    "                            dp[row][j] = max(dp[row][j],dp[row+1][k]+bin(j).count('1'))\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n=len(seats),len(seats[0])\n",
    "        dp=[[0]*(1<<n) for _ in range(m+1)]\n",
    "        arr=[0]*m\n",
    "        for i in range(m):\n",
    "            mask=0\n",
    "            for j in range(n):\n",
    "                if seats[i][j]==\"#\": mask|=(1<<j)\n",
    "            arr[i]=mask\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(1<<n):\n",
    "                if not j&arr[i] and not j&(j>>1) and not j&(j<<1):\n",
    "                    #可以坐人\n",
    "                    for k in range(1<<n):\n",
    "                        if not j&(k<<1) and not j&(k>>1):\n",
    "                            dp[i][j]=max(dp[i][j],dp[i+1][k]+bin(j).count(\"1\"))\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n=len(seats),len(seats[0])\n",
    "        dp=[[0]*(1<<n) for _ in range(m+1)]\n",
    "        arr=[0]*m\n",
    "        for i in range(m):\n",
    "            mask=0\n",
    "            for j in range(n):\n",
    "                if seats[i][j]==\"#\": mask|=(1<<j) \n",
    "            arr[i]=mask\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(1<<n):\n",
    "                if not j&arr[i] and not j&(j>>1) and not j&(j<<1):\n",
    "                    for k in range(1<<n):\n",
    "                        if not j&(k<<1) and not j&(k>>1):\n",
    "                            dp[i][j]=max(dp[i][j],dp[i+1][k]+bin(j).count(\"1\"))\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        n, m = len(seats), len(seats[0])\n",
    "        validStates, cnt = [], []\n",
    "        banned = [0] * n\n",
    "        for i in range(n):\n",
    "            mask = 0\n",
    "            for j in range(m):\n",
    "                if seats[i][j] == \"#\":\n",
    "                    mask |= (1 << j)\n",
    "            banned[i] = mask\n",
    "        for state in range(1 << m):\n",
    "            if not (state & (state << 1) or state & (state >> 1)):\n",
    "                validStates.append(state)\n",
    "                cnt.append(bin(state).count(\"1\"))\n",
    "        from_ = [[] for _ in range(len(validStates))]\n",
    "        for i, x in enumerate(validStates):\n",
    "            for j, y in enumerate(validStates):\n",
    "                if not (x & (y << 1) or x & (y >> 1)):\n",
    "                    from_[i].append(j)\n",
    "        f = [[-inf] * len(validStates) for _ in range(n)]\n",
    "        for i, mask in enumerate(validStates):\n",
    "            if mask & (banned[0]): continue\n",
    "            f[0][i] = cnt[i]\n",
    "        for i in range(1,n):\n",
    "            for j in range(len(validStates)):\n",
    "                mask = validStates[j]\n",
    "                if mask & banned[i]: continue\n",
    "                for k in from_[j]:\n",
    "                    f[i][j] = max(f[i][j], f[i - 1][k] + cnt[j])\n",
    "        return max(0, max(f[n - 1][i] for i in range(len(validStates))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0]),\n",
    "        dp = [[0]*(1 << n) for _ in range(m+1)] \n",
    "        a = [reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#'])  for i in range(m)]\n",
    "        for row in range(m)[::-1]:\n",
    "            for j in range(1 << n):\n",
    "                if not j & j<<1 and not j&j>>1 and not j & a[row]: \n",
    "                    for k in range(1 << n):\n",
    "                        if not j&k<<1 and not j&k>>1:\n",
    "                            dp[row][j] = max(dp[row][j], dp[row+1][k] + bin(j).count('1'))\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "\n",
    "        dp = [[float('-inf')] * (1 << n) for _ in range(m)]\n",
    "\n",
    "        def check(ii, j):\n",
    "            mask = (1 << n) - 1\n",
    "            for i in range(n):\n",
    "                if j & (1 << i) and seats[ii][i] == '#':\n",
    "                    return False\n",
    "            #  1100\n",
    "            # 11000\n",
    "            #110000\n",
    "\n",
    "            if ((j << 1) & j & mask) or ((j >> 1) & j & mask):\n",
    "                return False\n",
    "            else:\n",
    "                return True  \n",
    "\n",
    "\n",
    "        for j in range(len(dp[0])):\n",
    "            if check(0, j):\n",
    "                dp[0][j] = bin(j).count('1')\n",
    "            else:\n",
    "                dp[0][j] = float('-inf')\n",
    "\n",
    "        def ck(ci, cj, pi, pj):\n",
    "            mask = (1 << n) - 1\n",
    "            # for i in range(n):\n",
    "            #     if cj & (1 << i) and seats[ci][i] == '#':\n",
    "            #         return False\n",
    "            \n",
    "            # if ((cj << 1) & cj & mask) or ((cj >> 1) & cj & mask):\n",
    "            #     return False\n",
    "            \n",
    "            # 010100\n",
    "            # 001000\n",
    "\n",
    "            if ((cj << 1) & pj & mask) or ((cj >> 1) & pj & mask):\n",
    "                return False\n",
    "            \n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        \n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                jCnt = bin(j).count('1')\n",
    "                if not check(i, j):\n",
    "                    continue\n",
    "                for k in range(len(dp[0])):\n",
    "                    if ck(i, j, i - 1, k):\n",
    "                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + jCnt)\n",
    "\n",
    "\n",
    "\n",
    "        return max(0, max(dp[-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        valid_seats = [int(''.join(['1' if seat == '.' else '0' for seat in row]), 2) for row in seats]\n",
    "\n",
    "        def count_bits(x):\n",
    "            count = 0\n",
    "            while x:\n",
    "                x &= x - 1\n",
    "                count += 1\n",
    "            return count\n",
    "\n",
    "        dp = [[-1] * (1 << n) for _ in range(m)]\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            if mask & valid_seats[0] == mask and mask & (mask >> 1) == 0:\n",
    "                dp[0][mask] = count_bits(mask)\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for mask in range(1 << n):\n",
    "                if mask & valid_seats[i] == mask and mask & (mask >> 1) == 0:\n",
    "                    for prev_mask in range(1 << n):\n",
    "                        if dp[i - 1][prev_mask] != -1 and not (mask & (prev_mask >> 1)) and not (mask & (prev_mask << 1)):\n",
    "                            dp[i][mask] = max(dp[i][mask], dp[i - 1][prev_mask] + count_bits(mask))\n",
    "\n",
    "        return max(dp[-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        new_seats = []\n",
    "        for i in range(m):\n",
    "            t = 1\n",
    "            res = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if seats[i][j] == '.':\n",
    "                    res += t\n",
    "                t *= 2\n",
    "            new_seats.append(res)\n",
    "\n",
    "\n",
    "        def validateSelf(pattern):\n",
    "            return (pattern & (pattern << 1)) == 0 and (pattern & (pattern >> 1)) == 0\n",
    "\n",
    "        def validatePatterns(prev, curr):\n",
    "            return prev & curr << 1 == 0 and prev & curr >> 1 == 0\n",
    "\n",
    "        def count_ones(num):\n",
    "            res = 0\n",
    "            while num != 0:\n",
    "                res += 1\n",
    "                num = (num - 1) & num\n",
    "            return res\n",
    "        \n",
    "        dp = [[0] * (1 << n) for _ in range(m)]\n",
    "\n",
    "        for pattern in range(1 << n):\n",
    "            pattern = pattern & new_seats[0]\n",
    "            if not validateSelf(pattern):\n",
    "                continue\n",
    "            dp[0][pattern] = count_ones(pattern)\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for curr_pattern in range(1 << n):\n",
    "                curr_pattern = curr_pattern & new_seats[i]\n",
    "                if not validateSelf(curr_pattern):\n",
    "                    continue\n",
    "                for prev_pattern in range(1 << n):\n",
    "                    prev_pattern = prev_pattern & new_seats[i - 1]\n",
    "                    if not validateSelf(prev_pattern) or not validatePatterns(curr_pattern, prev_pattern):\n",
    "                        continue\n",
    "                    dp[i][curr_pattern] = max(dp[i][curr_pattern], dp[i - 1][prev_pattern] + count_ones(curr_pattern))\n",
    "        return max(dp[m - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        MX = (1 << n) - 1\n",
    "        dp = [[0] * MX for _ in range(m + 1)]\n",
    "        grid = [reduce(lambda x, y:x|(1 << y), [0] + [j for j in range(n) if seats[i][j] == '#']) for i in range(m)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(MX):\n",
    "                # 验证当前状态是否在一行上满足要求\n",
    "                if not grid[i] & j and not j & (j << 1) and not j & (j >> 1):\n",
    "                    for k in range(MX):\n",
    "                        # 验证当前状态是否和上一行冲突\n",
    "                        if not (k >> 1) & j and not (k << 1) & j:\n",
    "                            dp[i][j] = max(dp[i][j], dp[i + 1][k] + j.bit_count())\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n=len(seats),len(seats[0])\n",
    "        dp=[[0]*(1<<n) for _ in range(m+1)]\n",
    "        arr=[0]*m\n",
    "        for i in range(m):\n",
    "            mask=0\n",
    "            for j in range(n):\n",
    "                if seats[i][j]==\"#\": mask|=(1<<j)\n",
    "            arr[i]=mask\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(1<<n):\n",
    "                if not j&arr[i] and not j&(j>>1) and not j&(j<<1):\n",
    "                    #可以坐人\n",
    "                    for k in range(1<<n):\n",
    "                        if not j&(k<<1) and not j&(k>>1):\n",
    "                            dp[i][j]=max(dp[i][j],dp[i+1][k]+bin(j).count(\"1\"))\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        new_seats = []\n",
    "        for i in range(m):\n",
    "            t = 1\n",
    "            res = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if seats[i][j] == '.':\n",
    "                    res += t\n",
    "                t *= 2\n",
    "            new_seats.append(res)\n",
    "\n",
    "\n",
    "        def validateSelf(pattern):\n",
    "            return (pattern & (pattern << 1)) == 0 and (pattern & (pattern >> 1)) == 0\n",
    "\n",
    "        def validatePatterns(prev, curr):\n",
    "            return prev & curr << 1 == 0 and prev & curr >> 1 == 0\n",
    "        \n",
    "        dp = [[0] * (1 << n) for _ in range(m)]\n",
    "\n",
    "        for pattern in range(1 << n):\n",
    "            pattern = pattern & new_seats[0]\n",
    "            if not validateSelf(pattern):\n",
    "                continue\n",
    "            dp[0][pattern] = pattern.bit_count()\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for curr_pattern in range(1 << n):\n",
    "                curr_pattern = curr_pattern & new_seats[i]\n",
    "                if not validateSelf(curr_pattern):\n",
    "                    continue\n",
    "                for prev_pattern in range(1 << n):\n",
    "                    prev_pattern = prev_pattern & new_seats[i - 1]\n",
    "                    if not validateSelf(prev_pattern) or not validatePatterns(prev_pattern, curr_pattern):\n",
    "                        continue\n",
    "                    dp[i][curr_pattern] = max(dp[i][curr_pattern], dp[i - 1][prev_pattern] + curr_pattern.bit_count())\n",
    "        return max(dp[m - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('0' if x == '#' else '1' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        \n",
    "        g.append(0)\n",
    "\n",
    "        def check(s):# 检测相邻位置是否有人\n",
    "            for i in range(1 << n):\n",
    "                if s >> i & 1 and s>> i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # s.bit_count()\n",
    "        def bit_cnt(s):\n",
    "            cnt = 0\n",
    "            while s:\n",
    "                cnt += 1\n",
    "                s &= (s - 1)\n",
    "            return cnt\n",
    "\n",
    "        st = []\n",
    "        cnt = []\n",
    "        # 筛选满足相邻位置不能坐人的状态\n",
    "        for s in range(1 << n):\n",
    "            if check(s):\n",
    "                st.append(s)\n",
    "                cnt.append(bit_cnt(s))\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(2)] # 当前行状态是否合法与上一行相关,多算一行，就不用max(f[-1])\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for j,s1 in enumerate(st):\n",
    "                if g[i - 1] & s1 == s1: # 当前行状态合法\n",
    "                    # 枚举上一行可能的状态\n",
    "                    for k,s2 in enumerate(st):\n",
    "                        # s1 ｜ s2 不能有相邻的1\n",
    "                        if s2 & g[i - 2] == s2 and check(s1 | s2):\n",
    "                            f[i&1][s1] = max(f[i&1][s1],cnt[j] + f[i - 1&1][s2])\n",
    "\n",
    "        return f[m + 1 & 1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def bit_count(s):\n",
    "    return bin(s).count('1')\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s>>i & 1 and s>>i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('0' if x == '#' else '1' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        \n",
    "        g.append(0) # 最后加了一行，避免取max，后面会用到\n",
    "\n",
    "        def check(s):# 检测相邻位置是否有人\n",
    "            for i in range(1 << n):\n",
    "                if s >> i & 1 and s>> i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        st = []\n",
    "        cnt = []\n",
    "        # 筛选满足相邻位置不能坐人的状态\n",
    "        for s in range(1 << n):\n",
    "            if check(s):\n",
    "                st.append(s)\n",
    "                cnt.append(s.bit_count())\n",
    "        nxt = defaultdict(list)\n",
    "        # 预处理状态转移关系\n",
    "        for s1 in range(1 << n):\n",
    "            for s2 in range(1 << n):\n",
    "                if check(s1 | s2):\n",
    "                    nxt[s1].append(s2)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(2)] # 当前行状态是否合法与上一行相关,多算一行，就不用max(f[-1])\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for j,s1 in enumerate(st):\n",
    "                if g[i - 1] & s1 == s1: # 当前行状态合法\n",
    "                    # 转移\n",
    "                    for s2 in nxt[s1]:\n",
    "                        if s2 & g[i - 2] == s2:# i-2 = -1就是0，不用担心越界\n",
    "                            f[i&1][s1] = max(f[i&1][s1],cnt[j] + f[i - 1&1][s2])\n",
    "        return f[m + 1 & 1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m = len(seats)\n",
    "        n = len(seats[0])\n",
    "        pre_post_col_states = [[] for _ in range(2 ** m)]\n",
    "        for curr_state in range(2 ** m):\n",
    "            for pre_state in range(2 ** m):\n",
    "                if pre_state & curr_state == 0 and (pre_state >> 1) & curr_state == 0 and pre_state & (curr_state >> 1) == 0:\n",
    "                    pre_post_col_states[curr_state].append(pre_state)\n",
    "        #print(pre_post_col_states)\n",
    "        def does_state_fit_seats(state, j):\n",
    "            i = 1\n",
    "            while state:\n",
    "                curr_seat = seats[m - i][j]\n",
    "                if state & 1 == 1 and curr_seat == '#':\n",
    "                    return False\n",
    "                state >>= 1\n",
    "                i += 1\n",
    "            return True\n",
    "        def count_ones(state):\n",
    "            count = 0\n",
    "            while state:\n",
    "                count += state & 1\n",
    "                state >>= 1\n",
    "            return count\n",
    "        dp = [[0 for _ in range(2 ** m)] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for state in range(2 ** m):\n",
    "                if does_state_fit_seats(state, j):\n",
    "                    if j == 0:\n",
    "                        dp[j][state] = count_ones(state)\n",
    "                    else:\n",
    "                        dp[j][state] = count_ones(state) + max([dp[j - 1][pre_state] for pre_state in pre_post_col_states[state]])\n",
    "        #print(dp)\n",
    "        return max([dp[n - 1][pre_state] for pre_state in pre_post_col_states[0]])\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def bit_count(s):\n",
    "    cnt = 0\n",
    "    while s:\n",
    "        cnt += 1\n",
    "        s &= (s - 1)\n",
    "    return cnt\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s>>i & 1 and s>>i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        \n",
    "\n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s>>i & 1 and s>>i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def bit_count(s):\n",
    "            cnt = 0\n",
    "            while s:\n",
    "                cnt += 1\n",
    "                s &= (s - 1)\n",
    "            return cnt\n",
    "\n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def bit_count(s):\n",
    "    return bin(s).count('1')\n",
    "\n",
    "@cache\n",
    "def check(s):\n",
    "    for i in range(1 << 8):\n",
    "        if s>>i & 1 and s>>i + 1 & 1:\n",
    "            return False\n",
    "    return True\n",
    "        \n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 状态压缩技巧\n",
    "# 1.判断不相邻 status&(status>>1)==0\n",
    "# 2.判断当前位置是否有效（学生是否坐在座位好的位置）status&seatstatus == seatstatus\n",
    "from functools import lru_cache\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        n = len(seats)\n",
    "        m = len(seats[0])\n",
    "        allstatus = 1<<m\n",
    "        dp = [{} for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        ans = 0\n",
    "        seatstatus = [0]\n",
    "        for lineid in range(n):\n",
    "            nowstatus = 0\n",
    "            for i in range(m):\n",
    "                if seats[lineid][i] == '#':\n",
    "                    nowstatus |= 1<<i\n",
    "            seatstatus.append(nowstatus)\n",
    "            for prestatus in dp[lineid]:\n",
    "                for status in range(allstatus):\n",
    "                    # 计算得到前一排学生坐的位置和本行学生坐的位置\n",
    "                    stustatus = nowstatus^status\n",
    "                    prestustatus = seatstatus[lineid]^prestatus\n",
    "                    # 判断条件包含3个条件：1.在本行中学生都坐在座位好的位置；2.本行学生座位不相邻；3. 本行学生不坐在前一排的左后或右后方\n",
    "                    if nowstatus & status == nowstatus and (stustatus&(stustatus>>1) == 0 and stustatus&(stustatus<<1) == 0) and ((stustatus>>1)&prestustatus == 0 and (stustatus<<1)&prestustatus == 0):\n",
    "                        if status not in dp[lineid+1]:\n",
    "                            dp[lineid+1][status] = 0\n",
    "                        num = stustatus\n",
    "                        onenum = 0\n",
    "                        while num:\n",
    "                            onenum += num & 1\n",
    "                            num >>= 1\n",
    "                        dp[lineid+1][status] = max(dp[lineid+1][status], dp[lineid][prestatus] + onenum)\n",
    "                        ans = max(ans, dp[lineid+1][status])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "\n",
    "        dp = [[float('-inf')] * (1 << n) for _ in range(m)]\n",
    "\n",
    "        def check(j):\n",
    "            mask = (1 << n) - 1\n",
    "            for i in range(n):\n",
    "                if j & (1 << i) and seats[0][i] == '#':\n",
    "                    return False\n",
    "            #  1100\n",
    "            # 11000\n",
    "            #110000\n",
    "\n",
    "            if ((j << 1) & j & mask) or ((j >> 1) & j & mask):\n",
    "                return False\n",
    "            else:\n",
    "                return True  \n",
    "\n",
    "\n",
    "        for j in range(len(dp[0])):\n",
    "            if check(j):\n",
    "                dp[0][j] = bin(j).count('1')\n",
    "            else:\n",
    "                dp[0][j] = float('-inf')\n",
    "\n",
    "        def ck(ci, cj, pi, pj):\n",
    "            mask = (1 << n) - 1\n",
    "            for i in range(n):\n",
    "                if cj & (1 << i) and seats[ci][i] == '#':\n",
    "                    return False\n",
    "            \n",
    "            if ((cj << 1) & cj & mask) or ((cj >> 1) & cj & mask):\n",
    "                return False\n",
    "            \n",
    "            # 010100\n",
    "            # 001000\n",
    "\n",
    "            if ((cj << 1) & pj & mask) or ((cj >> 1) & pj & mask):\n",
    "                return False\n",
    "            \n",
    "\n",
    "            return True\n",
    "\n",
    "\n",
    "        \n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                jCnt = bin(j).count('1')\n",
    "                for k in range(len(dp[0])):\n",
    "                    if ck(i, j, i - 1, k):\n",
    "                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + jCnt)\n",
    "\n",
    "\n",
    "\n",
    "        return max(0, max(dp[-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        #剪枝\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,row_num,col):\n",
    "            ans=0\n",
    "            for scheme in range(1<<col):\n",
    "                #剪枝，坏的位置上做了人，或者相邻位置做了人\n",
    "                if scheme&~x or scheme&(scheme<<1):continue\n",
    "                tmp=0\n",
    "                for j in range(8):\n",
    "                    if (1<<j)&scheme:tmp+=1\n",
    "                # if row_num==len(seats)-1:ans=max(ans,tmp)\n",
    "                if row_num==len(comps)-1:ans=max(ans,tmp)\n",
    "                else:\n",
    "                    next_seats=comps[row_num+1]\n",
    "                    next_seats&=~(scheme<<1)#左右相邻位置不能在做人\n",
    "                    next_seats&=~(scheme>>1)\n",
    "                    ans=max(ans,tmp+dfs(next_seats,row_num+1,col))\n",
    "            return ans\n",
    "        def compress(row):\n",
    "            ans=0\n",
    "            for c in row:\n",
    "                ans<<=1#坏了的位置用0表示，可以做的位置用1表示\n",
    "                if c=='.':ans+=1\n",
    "            return ans\n",
    "        comps=[compress(i)for i in seats]\n",
    "        return dfs(comps[0],0,len(seats[0]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def bit_count(s):\n",
    "    return s.bit_count()\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s>>i & 1 and s>>i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(8 * 2 ** 8)\n",
    "    def f(self, X, row_num, width):\n",
    "        ans = 0\n",
    "        for scheme in range(1 << width):\n",
    "            if scheme & ~X or scheme & (scheme << 1):\n",
    "                continue\n",
    "            curans = 0\n",
    "            for j in range(8):\n",
    "                if (1 << j) & scheme:\n",
    "                    curans += 1\n",
    "            if row_num == len(self.seats) - 1:\n",
    "                ans = max(ans, curans)\n",
    "            else:\n",
    "                next_seats = self.seats[row_num + 1]\n",
    "                next_seats &= ~(scheme << 1)\n",
    "                next_seats &= ~(scheme >> 1)\n",
    "                ans = max(ans, curans + self.f(next_seats, row_num + 1, width))\n",
    "        return ans\n",
    "\n",
    "    def compress(self, row):\n",
    "        ans = 0\n",
    "        for c in row:\n",
    "            ans <<= 1\n",
    "            if c == '.':\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        self.seats = [self.compress(row) for row in seats]\n",
    "        return self.f(self.seats[0], 0, len(seats[0]))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m=len(seats)\n",
    "        n=len(seats[0])\n",
    "        broken=[]\n",
    "        for a in seats:\n",
    "            state=0\n",
    "            for j in range(len(a)):\n",
    "                if a[j]==\"#\":\n",
    "                  #  print(j)\n",
    "                    state=state|(1<<j)\n",
    "            broken.append(state)\n",
    "           \n",
    "        allstate=(1<<n)\n",
    "\n",
    "        dp=[[0]*allstate for _ in range(m+1)]\n",
    "        #dp[0][0]=0\n",
    "        for s in range(allstate):\n",
    "            if s&broken[0] or \"11\" in bin(s) : \n",
    "                continue\n",
    "            dp[1][s]=bin(s).count(\"1\")\n",
    "\n",
    "        for i in range(2,m+1):\n",
    "            for s in range(allstate):\n",
    "                if s&broken[i-1] or \"11\" in bin(s):\n",
    "                  #  print(i,bin(s))\n",
    "                    continue\n",
    "               # print(i,bin(s),bin(broken[i-1]))\n",
    "                for s1 in range(allstate):\n",
    "                    if s1&broken[i-2] or \"11\" in bin(s1):\n",
    "                        continue\n",
    "                    #print(i,bin(s),9)\n",
    "                    if (s1>>1)&s or ((s1<<1)&((1<<n)-1))&s:\n",
    "                         continue\n",
    "                    #print(i-1,bin(s1),dp[i-1][s1]) \n",
    "                   # print(i,bin(s)) \n",
    "                    cnt=bin(s).count(\"1\")\n",
    "                    dp[i][s]=max(dp[i][s],dp[i-1][s1]+cnt)\n",
    "        #print(dp)\n",
    "      #  print(2&1)\n",
    "        return max(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0]),\n",
    "        dp = [[0]*(1 << n) for _ in range(m+1)]  # 状态数组 dp\n",
    "        a = [reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#'])  for i in range(m)] # 将 # 设为 1，当遇到 . 时与运算结果为 0，表示可以坐人\n",
    "        # print(a)\n",
    "        for row in range(m)[::-1]: # 倒着遍历\n",
    "            for j in range(1 << n):\n",
    "                if not j & j<<1 and not j&j>>1 and not j & a[row]: # j & a[row]代表该位置可以坐人，j & j<<1 and not j&j>>1 表示该位置左右没人可以坐的\n",
    "                    for k in range(1 << n):\n",
    "                        if not j&k<<1 and not j&k>>1: # j状态的左上和右上没有人\n",
    "                            dp[row][j] = max(dp[row][j], dp[row+1][k] + bin(j).count('1'))\n",
    "        # print(dp)\n",
    "        return max(dp[0])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('0' if x == '#' else '1' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        \n",
    "        g.append(0)\n",
    "\n",
    "        def check(s):# 检测相邻位置是否有人\n",
    "            for i in range(1 << n):\n",
    "                if s >> i & 1 and s>> i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # s.bit_count()\n",
    "        def bit_cnt(s):\n",
    "            cnt = 0\n",
    "            while s:\n",
    "                cnt += 1\n",
    "                s &= (s - 1)\n",
    "            return cnt\n",
    "\n",
    "        st = []\n",
    "        cnt = []\n",
    "        # 筛选满足相邻位置不能坐人的状态\n",
    "        for s in range(1 << n):\n",
    "            if check(s):\n",
    "                st.append(s)\n",
    "                cnt.append(bit_cnt(s))\n",
    "        nxt = defaultdict(list)\n",
    "        # 预处理状态转移关系\n",
    "        for s1 in range(1 << n):\n",
    "            for s2 in range(1 << n):\n",
    "                if check(s1 | s2):\n",
    "                    nxt[s1].append(s2)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(2)] # 当前行状态是否合法与上一行相关,多算一行，就不用max(f[-1])\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for j,s1 in enumerate(st):\n",
    "                if g[i - 1] & s1 == s1: # 当前行状态合法\n",
    "                    # 转移\n",
    "                    for s2 in nxt[s1]:\n",
    "                        if s2 & g[i - 2] == s2:\n",
    "                            f[i&1][s1] = max(f[i&1][s1],cnt[j] + f[i - 1&1][s2])\n",
    "        return f[m + 1 & 1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        \"\"\" dynamic programming. 状态压缩\n",
    "        我根据acwing_291 写出。leetcode 解题中 都是 dp[i][state] 从 0 --> i 行，如果第i 行坐法为 state （student坐好 为1，否则为 0）的最多 坐的 所有 学生数。而我则是 dp[j][state]: 从 0 --> j 列，如果第j 列坐法为 state （student坐好 为1，否则为 0）的最多 坐的 所有 学生数\n",
    "        \"\"\"\n",
    "        m = len(seats)\n",
    "        n = len(seats[0])\n",
    "        # 预处理：\n",
    "        # pre_post_col_states：index 是 当前列的 state，values list 是 前一列 可行 的 states\n",
    "        # pre_state & curr_state == 0：同行不能同时为1\n",
    "        # (pre_state >> 1) & curr_state == 0 and pre_state & (curr_state >> 1) == 0：斜上方不能同时为1\n",
    "        pre_post_col_states = [[] for _ in range(2 ** m)]\n",
    "        for curr_state in range(2 ** m):\n",
    "            for pre_state in range(2 ** m):\n",
    "                if pre_state & curr_state == 0 and (pre_state >> 1) & curr_state == 0 and pre_state & (curr_state >> 1) == 0:\n",
    "                    pre_post_col_states[curr_state].append(pre_state)\n",
    "        #print(pre_post_col_states)\n",
    "        def does_state_fit_seats(state, j):\n",
    "            i = 1\n",
    "            while state:\n",
    "                curr_seat = seats[m - i][j]\n",
    "                if state & 1 == 1 and curr_seat == '#':\n",
    "                    return False\n",
    "                state >>= 1\n",
    "                i += 1\n",
    "            return True\n",
    "        def count_ones(state):\n",
    "            count = 0\n",
    "            while state:\n",
    "                count += state & 1\n",
    "                state >>= 1\n",
    "            return count\n",
    "        # dp[j][state]: 从 0 --> j 列，如果第j 列坐法为 state （student坐好 为1，否则为 0）的最多 坐的 所有 学生数\n",
    "        dp = [[0 for _ in range(2 ** m)] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for state in range(2 ** m):\n",
    "                if does_state_fit_seats(state, j):\n",
    "                    # 如果当前列 坐的学生们 为 state 时 能够有椅子坐\n",
    "                    if j == 0:\n",
    "                        # 如果是 第一列，这些state 都是 valid 的，计算 这些 states 都有多少个 1，就是 有多少个学生\n",
    "                        dp[j][state] = count_ones(state)\n",
    "                    else:\n",
    "                        # 如果是 其他 列，dp[j][curr_state] = 当前列 为 curr_state 有多少学生 （1的count） + 从 0 --> j - 1 列，第j - 1 列 所有 valid 的  pre_state 中最多 坐的 所有 学生数\n",
    "                        dp[j][state] = count_ones(state) + max([dp[j - 1][pre_state] for pre_state in pre_post_col_states[state]])\n",
    "        #print(dp)\n",
    "        # return 最后 一列 最大的 dp 值，等价于 dp[n][0]\n",
    "        return max([dp[n - 1][pre_state] for pre_state in pre_post_col_states[0]])\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(X, row, width):\n",
    "            ans = 0\n",
    "            for scheme in range(1 << width):\n",
    "                if scheme & ~X != 0 or (scheme) & (scheme << 1):\n",
    "                    continue\n",
    "                \n",
    "                curan = 0\n",
    "\n",
    "                for j in range(8):\n",
    "                    if (1 << j) & scheme:\n",
    "                        curan += 1\n",
    "                \n",
    "                if row == len(seats) - 1:\n",
    "                    ans = max(ans, curan)\n",
    "                else:\n",
    "                    next_seat = s[row + 1]\n",
    "                    next_seat &= ~(scheme << 1)\n",
    "                    next_seat &= ~(scheme >> 1)\n",
    "                    ans = max(ans, curan + dfs(next_seat, row + 1, width))\n",
    "            \n",
    "            return ans\n",
    "\n",
    "\n",
    "\n",
    "        def compress(s):\n",
    "            ans = 0\n",
    "            for c in s:\n",
    "                ans <<= 1\n",
    "                if c == '.':\n",
    "                    ans += 1\n",
    "                \n",
    "            return ans\n",
    "\n",
    "\n",
    "        s = [compress(seat) for seat in seats]\n",
    "        return dfs(s[0], 0, len(seats[0]))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        row, col = len(seats), len(seats[0])\n",
    "        dp = [[0 for _ in range(1 << col)] for _ in range(row)]\n",
    "\n",
    "        def judgeSeatAble(floor, state):\n",
    "            for j in range(col):\n",
    "                #看是不是在不能坐的地方坐了人\n",
    "                if seats[floor][j] == '#' and (state & (1 << j)) != 0:\n",
    "                   return False\n",
    "            return True\n",
    "\n",
    "        def judgeCheatAble(state):\n",
    "            lastHasMan = False\n",
    "            \n",
    "            for j in range(col):\n",
    "                #看是不是有相邻位置坐了人\n",
    "                if (state & (1 << j)) != 0 and not lastHasMan:\n",
    "                    lastHasMan = True\n",
    "                elif (state & (1 << j)) == 0:\n",
    "                    lastHasMan = False\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "            return True\n",
    "        \n",
    "        def bitCount(n):\n",
    "            c = 0\n",
    "            for i in range(col):\n",
    "                if (n & (1 << i) != 0):\n",
    "                    c += 1\n",
    "            return c\n",
    "        \n",
    "        def transform(state, n):\n",
    "            for i in range(col):\n",
    "                if (n & (1 << i)) != 0:\n",
    "                    if i < col - 1:\n",
    "                        t = state\n",
    "                        state = state & (1 << (i + 1))\n",
    "                        state = ~state\n",
    "                        state = state & t\n",
    "                    if i > 0:\n",
    "                        t = state\n",
    "                        state = state & (1 << (i - 1))\n",
    "                        state = ~state\n",
    "                        state = state & t\n",
    "            return state\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(1 << col):\n",
    "                if judgeCheatAble(j) and judgeSeatAble(i, j):\n",
    "                    cnt = bitCount(j)\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = cnt\n",
    "                    else:\n",
    "                        #需要求出上一层状态\n",
    "                        for k in range(1 << col):\n",
    "                            if judgeCheatAble(k) and judgeSeatAble(i - 1, k):\n",
    "                                # 需要左上和右上的置为0\n",
    "                                dp[i][j] = max(dp[i][j], cnt + dp[i - 1][transform(k, j)])\n",
    "        \n",
    "        maxx = 0\n",
    "        for i in range(1 << col):\n",
    "            maxx = max(maxx, dp[row - 1][i])\n",
    "        return maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0]),\n",
    "        dp = [[0]*(1 << n) for _ in range(m+1)]  # 状态数组 dp\n",
    "        a = [reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#'])  for i in range(m)] \n",
    "        # 将 # 设为 1，当遇到 . 时与运算结果为 0，表示可以坐人\n",
    "        # print(a)\n",
    "        for row in range(m)[::-1]: # 倒着遍历\n",
    "            for j in range(1 << n):\n",
    "                if not j & j<<1 and not j&j>>1 and not j & a[row]: \n",
    "                    # j & a[row]代表该位置可以坐人，j & j<<1 and not j&j>>1 表示该位置左右没人可以坐的\n",
    "                    for k in range(1 << n):\n",
    "                        if not j&k<<1 and not j&k>>1: # j状态的左上和右上没有人\n",
    "                            dp[row][j] = max(dp[row][j], dp[row+1][k] + bin(j).count('1'))\n",
    "        # print(dp)\n",
    "        return max(dp[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            g.append(int(''.join('1' if x == '.' else '0' for x in row),2))\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g.append(0)\n",
    "        st = []\n",
    "        def check(s):\n",
    "            for i in range(n):\n",
    "                if s>>i & 1 and s >> i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            if check(i):\n",
    "                st.append(i)\n",
    "        \n",
    "        def bit_count(s):\n",
    "            return bin(s).count('1')\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "        for i in range(1,m + 2):\n",
    "            for s1 in st:\n",
    "                if s1 & g[i - 1] == s1:\n",
    "                    for s2 in st:\n",
    "                        if s2 & g[i - 2] == s2 and check(s1 | s2):\n",
    "                            f[i][s1] = max(f[i][s1],f[i - 1][s2] + bit_count(s1))\n",
    "\n",
    "        return f[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "\n",
    "        def bit_count(s):\n",
    "            return bin(s).count('1')\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s >> i & 1 and s >> i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        a = set()\n",
    "        for i in range(1 << n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "        \n",
    "        f = [[0]*(1<<n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s1 in a:\n",
    "                if s1 & g[i - 1] == s1:\n",
    "                    for s2 in a:\n",
    "                        if s2 & g[i - 2] == s2 and s1 | s2 in a:\n",
    "                            f[i][s1] = max(f[i][s1],f[i - 1][s2] + bit_count(s1))\n",
    "        return f[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        case = 1 << n\n",
    "        dp = [0] * case\n",
    "        for i in range(m):\n",
    "            new = [0] * case\n",
    "            mask = 0\n",
    "            for j in range(n):\n",
    "                if seats[i][j] == '#':\n",
    "                    mask |= 1 << j\n",
    "            for cur in range(case):\n",
    "                if cur & mask or cur & (cur >> 1) or cur & (cur << 1):\n",
    "                    continue\n",
    "                for pre in range(case):\n",
    "                    if cur & (pre >> 1) or cur & (pre << 1):\n",
    "                        continue\n",
    "                    new[cur] = max(new[cur], dp[pre] + bin(cur).count('1'))\n",
    "            dp = new \n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        vis = [0] * m \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if seats[i][j] == '.':\n",
    "                    vis[i] |= 1 << j \n",
    "        dp = [[0] * (1 << n) for _ in range(m+1)]\n",
    "        s = vis[0]\n",
    "        while s > 0:\n",
    "            flag = 1\n",
    "            for j in range(n-1):\n",
    "                if (s >> j) & 3 == 3:\n",
    "                    flag = 0 \n",
    "                    break \n",
    "            if flag:\n",
    "                dp[0][s] = str(bin(s)).count('1') \n",
    "            s = (s - 1) & vis[0]\n",
    "        #print(dp[0])\n",
    "        for i in range(1, m):\n",
    "            s = vis[i]\n",
    "            while s > 0:\n",
    "                flag = 1 \n",
    "                for j in range(n-1):\n",
    "                    if (s >> j) & 3 == 3:\n",
    "                        flag = 0\n",
    "                        break \n",
    "                if flag:\n",
    "                    s1 = vis[i-1] \n",
    "                    while s1 > 0:\n",
    "                        if dp[i-1][s1] > 0:\n",
    "                            flag1 = 1\n",
    "                            for j in range(n-1):\n",
    "                                if (s1 >> j) & (s >> (j+1))&1 == 1 or (s1 >> (j+1)) & (s >> j)&1 == 1:\n",
    "                                    flag1 = 0 \n",
    "                                    break \n",
    "                            if flag1:\n",
    "                                dp[i][s] = max(dp[i][s], dp[i-1][s1] + str(bin(s)).count('1')) \n",
    "                        s1 = (s1 - 1) & vis[i-1] \n",
    "                    dp[i][s] = max(dp[i][s], dp[i-1][0] + str(bin(s)).count('1'))\n",
    "                s = (s - 1) & vis[i]\n",
    "            dp[i][0] = max(dp[i-1]) \n",
    "            #print(dp[i])\n",
    "        return max(dp[m-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        n = len(seats)\n",
    "        m = len(seats[0])\n",
    "        allstatus = 1<<m\n",
    "        dp = [{} for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        ans = 0\n",
    "        seatstatus = [0]\n",
    "        for lineid in range(n):\n",
    "            nowstatus = 0\n",
    "            for i in range(m):\n",
    "                if seats[lineid][i] == '#':\n",
    "                    nowstatus |= 1<<i\n",
    "            seatstatus.append(nowstatus)\n",
    "            for prestatus in dp[lineid]:\n",
    "                for status in range(allstatus):\n",
    "                    # 计算得到前一排学生坐的位置和本行学生坐的位置\n",
    "                    stustatus = nowstatus^status\n",
    "                    prestustatus = seatstatus[lineid]^prestatus\n",
    "                    # 判断条件包含3个条件：1.在本行中学生都坐在座位好的位置；2.本行学生座位不相邻；3. 本行学生不坐在前一排的左后或右后方\n",
    "                    if nowstatus & status == nowstatus and (stustatus&(stustatus>>1) == 0 and stustatus&(stustatus<<1) == 0) and ((stustatus>>1)&prestustatus == 0 and (stustatus<<1)&prestustatus == 0):\n",
    "                        if status not in dp[lineid+1]:\n",
    "                            dp[lineid+1][status] = 0\n",
    "                        num = stustatus\n",
    "                        onenum = 0\n",
    "                        while num:\n",
    "                            onenum += num & 1\n",
    "                            num >>= 1\n",
    "                        dp[lineid+1][status] = max(dp[lineid+1][status], dp[lineid][prestatus] + onenum)\n",
    "                        ans = max(ans, dp[lineid+1][status])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('0' if x == '#' else '1' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        \n",
    "        g.append(0)\n",
    "\n",
    "        def check(s):# 检测相邻位置是否有人\n",
    "            for i in range(1 << n):\n",
    "                if s >> i & 1 and s>> i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # s.bit_count()\n",
    "        @cache\n",
    "        def bit_cnt(s):\n",
    "            cnt = 0\n",
    "            while s:\n",
    "                cnt += 1\n",
    "                s &= (s - 1)\n",
    "            return cnt\n",
    "\n",
    "        st = []\n",
    "        cnt = []\n",
    "        # 筛选满足相邻位置不能坐人的状态\n",
    "        for s in range(1 << n):\n",
    "            if check(s):\n",
    "                st.append(s)\n",
    "                cnt.append(bit_cnt(s))\n",
    "        nxt = defaultdict(list)\n",
    "        # 预处理状态转移关系\n",
    "        for s1 in range(1 << n):\n",
    "            for s2 in range(1 << n):\n",
    "                if check(s1 | s2):\n",
    "                    nxt[s1].append(s2)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(2)] # 当前行状态是否合法与上一行相关,多算一行，就不用max(f[-1])\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for j,s1 in enumerate(st):\n",
    "                if g[i - 1] & s1 == s1: # 当前行状态合法\n",
    "                    # 转移\n",
    "                    for s2 in nxt[s1]:\n",
    "                        if s2 & g[i - 2] == s2:\n",
    "                            f[i&1][s1] = max(f[i&1][s1],cnt[j] + f[i - 1&1][s2])\n",
    "        return f[m + 1 & 1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def bit_count(s):\n",
    "    return bin(s).count('1')\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s>>i & 1 and s>>i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        vis = [0] * (m+1) \n",
    "        for i in range(1,m+1):\n",
    "            for j in range(n):\n",
    "                if seats[i-1][j] == '.':\n",
    "                    vis[i] |= 1 << j \n",
    "        dp = [[0] * (1 << n) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            s = vis[i]\n",
    "            while s > 0:\n",
    "                flag = 1 \n",
    "                for j in range(n-1):\n",
    "                    if (s >> j) & 3 == 3:\n",
    "                        flag = 0\n",
    "                        break \n",
    "                if flag:\n",
    "                    s1 = vis[i-1] \n",
    "                    while s1 > 0:\n",
    "                        if dp[i-1][s1] > 0:\n",
    "                            flag1 = 1\n",
    "                            for j in range(n-1):\n",
    "                                if (s1 >> j) & (s >> (j+1))&1 == 1 or (s1 >> (j+1)) & (s >> j)&1 == 1:\n",
    "                                    flag1 = 0 \n",
    "                                    break \n",
    "                            if flag1:\n",
    "                                dp[i][s] = max(dp[i][s], dp[i-1][s1] + str(bin(s)).count('1')) \n",
    "                        s1 = (s1 - 1) & vis[i-1] \n",
    "                    dp[i][s] = max(dp[i][s], dp[i-1][0] + str(bin(s)).count('1'))\n",
    "                s = (s - 1) & vis[i]\n",
    "            dp[i][0] = max(dp[i-1]) \n",
    "            #print(dp[i])\n",
    "        return max(dp[m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        g = []\n",
    "        for row in seats:\n",
    "            s = ''.join('1' if x == '.' else '0' for x in row)\n",
    "            g.append(int(s,2))\n",
    "        g.append(0)\n",
    "        \n",
    "        def check(s):\n",
    "            for i in range(1 << n):\n",
    "                if s>>i & 1 and s>>i + 1 & 1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def bit_count(s):\n",
    "            cnt = 0\n",
    "            while s:\n",
    "                cnt += 1\n",
    "                s &= (s - 1)\n",
    "            return cnt\n",
    "\n",
    "        a = set()\n",
    "        for i in range(1<<n):\n",
    "            if check(i):\n",
    "                a.add(i)\n",
    "\n",
    "        f = [[0]*(1 << n) for _ in range(m + 2)]\n",
    "\n",
    "        for i in range(1,m + 2):\n",
    "            for s in a:\n",
    "                if s & g[i - 1] == s:\n",
    "                    for s2 in a:\n",
    "                        if s2&g[i - 2] == s2 and (s | s2) in a:\n",
    "                            f[i][s] = max(f[i][s],f[i - 1][s2] + bit_count(s))\n",
    "        return f[-1][0] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(8 * 2 ** 8)\n",
    "    def f(self, X, row_num, width):\n",
    "        ans = 0\n",
    "        for scheme in range(1 << width):\n",
    "            if scheme & ~X or scheme & (scheme << 1):\n",
    "                continue\n",
    "            curans = 0\n",
    "            for j in range(8):\n",
    "                if (1 << j) & scheme:\n",
    "                    curans += 1\n",
    "            if row_num == len(self.seats) - 1:\n",
    "                ans = max(ans, curans)\n",
    "            else:\n",
    "                next_seats = self.seats[row_num + 1]\n",
    "                next_seats &= ~(scheme << 1)\n",
    "                next_seats &= ~(scheme >> 1)\n",
    "                ans = max(ans, curans + self.f(next_seats, row_num + 1, width))\n",
    "        return ans\n",
    "\n",
    "    def compress(self, row):\n",
    "        ans = 0\n",
    "        for c in row:\n",
    "            ans <<= 1\n",
    "            if c == '.':\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        self.seats = [self.compress(row) for row in seats]\n",
    "        return self.f(self.seats[0], 0, len(seats[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#参加考试的最大学生数，记忆化搜索，状压\n",
    "#输入：seats = [[\"#\",\".\",\"#\",\"#\",\".\",\"#\"],[\".\",\"#\",\"#\",\"#\",\"#\",\".\"],[\"#\",\".\",\"#\",\"#\",\".\",\"#\"]]输出：4\n",
    "#输入：seats = [[\".\",\"#\"],[\"#\",\"#\"],[\"#\",\".\"],[\"#\",\"#\"],[\".\",\"#\"]]输出：3\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        #剪枝\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,row_num,col):\n",
    "            ans=0\n",
    "            for scheme in range(1<<col):\n",
    "                #剪枝，坏的位置上做了人，或者相邻位置做了人\n",
    "                if scheme&~x or scheme&(scheme<<1):continue\n",
    "                tmp=0\n",
    "                for j in range(8):\n",
    "                    if (1<<j)&scheme:tmp+=1\n",
    "                # if row_num==len(seats)-1:ans=max(ans,tmp)\n",
    "                if row_num==len(comps)-1:ans=max(ans,tmp)\n",
    "                else:\n",
    "                    next_seats=comps[row_num+1]\n",
    "                    next_seats&=~(scheme<<1)#左右相邻位置不能在做人\n",
    "                    next_seats&=~(scheme>>1)\n",
    "                    ans=max(ans,tmp+dfs(next_seats,row_num+1,col))\n",
    "            return ans\n",
    "        def compress(row):\n",
    "            ans=0\n",
    "            for c in row:\n",
    "                ans<<=1#坏了的位置用0表示，可以做的位置用1表示\n",
    "                if c=='.':ans+=1\n",
    "            return ans\n",
    "        comps=[compress(i)for i in seats]\n",
    "        return dfs(comps[0],0,len(seats[0]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m,n = len(seats),len(seats[0])\n",
    "        z = []\n",
    "        for i in range(1 << n):\n",
    "            for j in range(1, n):\n",
    "                if (i >> j) & 1 and (i >> (j-1)) & 1:\n",
    "                    break\n",
    "            else:\n",
    "                z.append(i)\n",
    "        q = []\n",
    "        for i in range(m):\n",
    "            t = 0\n",
    "            for j in range(n):\n",
    "                t = (t << 1)\n",
    "                if seats[i][j] == '.':\n",
    "                    t = t | 1\n",
    "            q.append(t)\n",
    "        @cache\n",
    "        def f(p:int,i:int):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for k in z:\n",
    "                # if k & q[i] != q[i]:\n",
    "                #     continue\n",
    "                k = (k & q[i])\n",
    "                if  (k & (p >> 1)) != 0 or (k & (p << 1))!= 0:\n",
    "                    continue\n",
    "                res = max(res, k.bit_count() + f(k, i+1))\n",
    "            return res\n",
    "        return f(0, 0)\n",
    "\n",
    "s = Solution()\n",
    "s.maxStudents([[\"#\",\".\",\".\",\".\",\"#\"],\n",
    "              [\".\",\"#\",\".\",\"#\",\".\"],\n",
    "              [\".\",\".\",\"#\",\".\",\".\"],\n",
    "              [\".\",\"#\",\".\",\"#\",\".\"],\n",
    "              [\"#\",\".\",\".\",\".\",\"#\"]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(X, row, width):\n",
    "            ans = 0\n",
    "            for scheme in range(1 << width):\n",
    "                if scheme & ~X != 0 or (scheme) & (scheme << 1):\n",
    "                    continue\n",
    "                \n",
    "                curan = 0\n",
    "\n",
    "                for j in range(8):\n",
    "                    if (1 << j) & scheme:\n",
    "                        curan += 1\n",
    "                \n",
    "                if row == len(seats) - 1:\n",
    "                    ans = max(ans, curan)\n",
    "                else:\n",
    "                    next_seat = s[row + 1]\n",
    "                    next_seat &= ~(scheme << 1)\n",
    "                    next_seat &= ~(scheme >> 1)\n",
    "                    ans = max(ans, curan + dfs(next_seat, row + 1, width))\n",
    "            \n",
    "            return ans\n",
    "\n",
    "\n",
    "\n",
    "        def compress(s):\n",
    "            ans = 0\n",
    "            for c in s:\n",
    "                ans <<= 1\n",
    "                if c == '.':\n",
    "                    ans += 1\n",
    "                \n",
    "            return ans\n",
    "\n",
    "\n",
    "        s = [compress(seat) for seat in seats]\n",
    "        return dfs(s[0], 0, len(seats[0]))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最大流\n",
    "'''\n",
    "from collections import *\n",
    "from math import *\n",
    "class FlowEdge:\n",
    "    def __init__(self, x:int, y:int, cap:int):\n",
    "        self.x, self.y, self.cap, self.flow = x, y, cap, 0\n",
    "class Dinic:\n",
    "    def __init__(self, n, edges, s=0, t=0):\n",
    "        self.edges = []\n",
    "        self.g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges: self.add_edge(x, y, w)\n",
    "        self.dq = deque()\n",
    "        self.level, self.ptr = [], []\n",
    "        self.s, self.t, self.n = s, t, n\n",
    "\n",
    "    def add_edge(self, x, y, cap) -> None:\n",
    "        m = len(self.edges)\n",
    "        self.edges.append(FlowEdge(x, y, cap))\n",
    "        self.edges.append(FlowEdge(y, x, 0))\n",
    "        self.g[x].append(m)\n",
    "        self.g[y].append(m+1)\n",
    "\n",
    "    def bfs(self) -> bool:\n",
    "        while self.dq:\n",
    "            x = self.dq.popleft()\n",
    "            for id in self.g[x]:\n",
    "                if self.edges[id].cap - self.edges[id].flow < 1: continue\n",
    "                if self.level[self.edges[id].y] != -1: continue\n",
    "                self.level[self.edges[id].y] = self.level[x] + 1\n",
    "                self.dq.append(self.edges[id].y)\n",
    "        return self.level[self.t] != -1\n",
    "\n",
    "    def dfs(self, x, pushed) -> int:\n",
    "        if not pushed: return 0\n",
    "        if x == self.t: return pushed\n",
    "        for cid in range(self.ptr[x], len(self.g[x])):\n",
    "            id = self.g[x][cid]\n",
    "            y = self.edges[id].y\n",
    "            if self.level[x] + 1 != self.level[y] or self.edges[id].cap - self.edges[id].flow < 1: continue\n",
    "            tr = self.dfs(y, min(pushed, self.edges[id].cap - self.edges[id].flow))\n",
    "            if not tr: continue\n",
    "            self.edges[id].flow += tr\n",
    "            self.edges[id ^ 1].flow -= tr\n",
    "            self.ptr[x] += 1\n",
    "            return tr\n",
    "        return 0\n",
    "\n",
    "    def flow(self) -> int:\n",
    "        rnt = 0\n",
    "        while True:\n",
    "            self.level = [-1] * self.n\n",
    "            self.level[self.s] = 0\n",
    "            self.dq.append(self.s)\n",
    "            if not self.bfs(): break\n",
    "            self.ptr = [0] * self.n\n",
    "            pushed = self.dfs(self.s, inf)\n",
    "            while pushed:\n",
    "                rnt += pushed\n",
    "                pushed = self.dfs(self.s, inf)\n",
    "        return rnt\n",
    "\n",
    "# if __name__==\"__main__\":\n",
    "#     m, n = [int(x) for x in input().split()]\n",
    "#     edges = []\n",
    "#     for _ in range(m):\n",
    "#         x, y, w = [int(k) for k in input().split()]\n",
    "#         edges.append((x-1, y-1, w))\n",
    "#     dinic = Dinic(n, edges, 0, n-1)\n",
    "#     print(dinic.flow())\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        N = 100\n",
    "        src = m * N + 1\n",
    "        dst = src + 1\n",
    "        \n",
    "\n",
    "        odd, even = set(), set()\n",
    "        edges = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if seats[i][j] == '.':\n",
    "                    if j % 2 == 1: \n",
    "                        odd.add((i, j))\n",
    "                        edges.append((src, i * N + j, 1))\n",
    "                    else: \n",
    "                        even.add((i, j))\n",
    "                        edges.append((i * N + j, dst, 1))\n",
    "\n",
    "        for x, y in odd:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in even:\n",
    "                    edges.append((x * N + y, nx * N + ny,  1))\n",
    "        \n",
    "        for x, y in even:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in odd:\n",
    "                    edges.append((nx * N + ny, x * N + y,   1))\n",
    " \n",
    "        dinic = Dinic(dst+1, edges, src, dst)\n",
    "        flow = dinic.flow()\n",
    "        return len(odd) + len(even) - flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    @functools.lru_cache(8 * 2 ** 8)\n",
    "    def f(self, X, row_num, width):\n",
    "        ans = 0\n",
    "        for scheme in range(1 << width):\n",
    "            if scheme & ~X or scheme & (scheme << 1):\n",
    "                continue\n",
    "            curans = 0\n",
    "            for j in range(8):\n",
    "                if (1 << j) & scheme:\n",
    "                    curans += 1\n",
    "            if row_num == len(self.seats) - 1:\n",
    "                ans = max(ans, curans)\n",
    "            else:\n",
    "                next_seats = self.seats[row_num + 1]\n",
    "                next_seats &= ~(scheme << 1)\n",
    "                next_seats &= ~(scheme >> 1)\n",
    "                ans = max(ans, curans + self.f(next_seats, row_num + 1, width))\n",
    "        return ans\n",
    "\n",
    "    def compress(self, row):\n",
    "        ans = 0\n",
    "        for c in row:\n",
    "            ans <<= 1\n",
    "            if c == '.':\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        self.seats = [self.compress(row) for row in seats]\n",
    "        return self.f(self.seats[0], 0, len(seats[0]))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        possible = []\n",
    "        for row in seats:\n",
    "            cur = 0\n",
    "            for c in row:\n",
    "                cur <<= 1\n",
    "                if c == '.':\n",
    "                    cur += 1\n",
    "            possible.append(cur)\n",
    "        @lru_cache(maxsize=None)\n",
    "        def recur(rnum,lastSts):\n",
    "            if rnum == len(seats):\n",
    "                return 0\n",
    "            res = 0\n",
    "            for sts in range(1<<len(seats[0])):\n",
    "                if sts &(~possible[rnum]) or sts & (sts<<1):\n",
    "                    continue\n",
    "                if sts & (lastSts<<1) or sts & (lastSts>>1):\n",
    "                    continue\n",
    "                cur,curOnes = sts,0\n",
    "                while cur:\n",
    "                    if cur%2:\n",
    "                        curOnes += 1\n",
    "                    cur >>= 1\n",
    "                #print(sts,)\n",
    "                res = max(res,recur(rnum+1,sts)+curOnes)\n",
    "            return res\n",
    "        #print(possible)\n",
    "        return recur(0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最小费用最大流，洛谷 P3381\n",
    "'''\n",
    "from collections import *\n",
    "from math import *\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val, self.v, self.next, self.w = 0, 0, 0, 0\n",
    "    def __str__(self):\n",
    "        return \"{}, {}, {}, {}\".format(self.val, self.v, self.next, self.w)\n",
    "\n",
    "class Dinic:\n",
    "    def __init__(self, src, dst, n=5010):\n",
    "        self.nodes = [Node() for _ in range(2)]\n",
    "        self.top = 1\n",
    "        self.s, self.t = src, dst\n",
    "        self.N = n\n",
    "        self.head, self.vis, self.dist = [0] * self.N, [0] * self.N, [inf] * self.N\n",
    "        self.cost, self.maxflow = 0, 0\n",
    "    \n",
    "    def _add_edge(self, u, v, val, w):\n",
    "        self.nodes.append(Node())\n",
    "        self.top += 1\n",
    "        self.nodes[self.top].v = v\n",
    "        self.nodes[self.top].w = w\n",
    "        self.nodes[self.top].val = val\n",
    "        self.nodes[self.top].next = self.head[u]\n",
    "        self.head[u] = self.top\n",
    "    \n",
    "    def add_edge(self, u, v, val, w=0):\n",
    "        self._add_edge(u , v, val, w)\n",
    "        self._add_edge(v, u, 0, -w)\n",
    "    \n",
    "    def spfa(self)->bool:\n",
    "        self.vis, self.dist = [0] * self.N, [inf] * self.N\n",
    "        self.dist[self.s], self.vis[self.s] = 0, 1\n",
    "        dq = deque([self.s])\n",
    "        \n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            self.vis[u] = 0\n",
    "            i = self.head[u]\n",
    "            while i:\n",
    "                d = self.nodes[i].v\n",
    "                if self.dist[u] + self.nodes[i].w < self.dist[d] and self.nodes[i].val:\n",
    "                    self.dist[d] = self.dist[u] + self.nodes[i].w\n",
    "                    if self.vis[d] == 0: \n",
    "                        dq.append(d)\n",
    "                        self.vis[d] = 1\n",
    "                i = self.nodes[i].next\n",
    "        return self.dist[self.t] != inf\n",
    "    \n",
    "    def dfs(self, u, flow)->int:\n",
    "        if u == self.t:\n",
    "            self.vis[self.t] = 1\n",
    "            self.maxflow += flow\n",
    "            return flow\n",
    "        used = 0\n",
    "        self.vis[u] = 1\n",
    "        i = self.head[u]\n",
    "        while i:\n",
    "            d = self.nodes[i].v\n",
    "            if (self.vis[d] == 0 or d == self.t) and self.nodes[i].val != 0 and self.dist[d] == self.dist[u] + self.nodes[i].w:\n",
    "                minflow = self.dfs(d, min(flow-used, self.nodes[i].val))\n",
    "                if minflow != 0:\n",
    "                    self.cost += self.nodes[i].w * minflow\n",
    "                    self.nodes[i].val -= minflow\n",
    "                    self.nodes[i^1].val += minflow\n",
    "                    used += minflow\n",
    "                if used == flow: break\n",
    "            i = self.nodes[i].next\n",
    "        return used\n",
    "\n",
    "    def get_max_flow_min_cost(self):\n",
    "        while self.spfa():\n",
    "            self.vis[self.t] = 1\n",
    "            while self.vis[self.t]:\n",
    "                self.vis = [0] * self.N\n",
    "                self.dfs(self.s, inf)\n",
    "        return self.maxflow, self.cost\n",
    "\n",
    "# if __name__ == '__main__':\n",
    "#     n, m, s, t = map(int, input().split())\n",
    "#     dinic = Dinic(s, t)\n",
    "#     for i in range(m):\n",
    "#         u, v, val, w = map(int, input().split())\n",
    "#         dinic.add_edge(u , v, val, w) # val->流量，w->费用\n",
    "#     ans, cost = dinic.get_max_flow_min_cost()\n",
    "#     print(ans, cost)\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        N = 100\n",
    "        src = m * N + 1\n",
    "        dst = src + 1\n",
    "        \n",
    "        dinic = Dinic(src, dst, dst+1)\n",
    "        odd, even = set(), set()\n",
    "        edges = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if seats[i][j] == '.':\n",
    "                    if j % 2 == 1: \n",
    "                        odd.add((i, j))\n",
    "                        dinic.add_edge(src, i * N + j, 1)\n",
    "                    else: \n",
    "                        even.add((i, j))\n",
    "                        dinic.add_edge(i * N + j, dst, 1)\n",
    "\n",
    "        for x, y in odd:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in even:\n",
    "                    dinic.add_edge(x * N + y, nx * N + ny,  1)\n",
    "        \n",
    "        for x, y in even:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in odd:\n",
    "                    dinic.add_edge(nx * N + ny, x * N + y, 1)\n",
    "        \n",
    "        flow, _ = dinic.get_max_flow_min_cost()\n",
    "        return len(odd) + len(even) - flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    @functools.lru_cache(8 * 2 ** 8)\n",
    "    def __dp(self, X, row_num, width):\n",
    "        \"\"\"\n",
    "        X: 当前行的座位布局\n",
    "        row_num: 行索引\n",
    "        width: 当前行有多少个座位\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        for scheme in range(1 << width):  # 1左移width长度：1 * 2 ** width；1是占位符，不参与运算，1后的0是当前是否坐人的标志初始化\n",
    "            if scheme & ~X or scheme & (scheme << 1):\n",
    "                # X是原本的座位，0代表坏的，1代表好的\n",
    "                # ~X，X取反，代表原先好的座位1变成了0\n",
    "                # scheme & ~X => True => 结果非0 => 座位是坏的位置处有人要坐\n",
    "                # scheme & (scheme << 1) => 相邻的位置有人坐\n",
    "                continue\n",
    "            # 坏座位处无人坐，且相邻座位没有学生\n",
    "            curans = 0\n",
    "            for j in range(8):\n",
    "                # 每个座位有 8 个可能的状态，分别对应四个方向（左、右、左上、右上）上的观察情况，以及每个方向上的是否有学生坐在相邻座位\n",
    "                if (1 << j) & scheme:\n",
    "                    curans += 1\n",
    "            if row_num == len(self.seats) - 1:\n",
    "                ans = max(ans, curans)\n",
    "            else:\n",
    "                # 计算下一行座位的状态，以便递归计算下一行的最大学生人数。\n",
    "                # 具体来说，这段代码用于确定下一行座位中哪些位置是可用的，以及哪些位置是被占用或不可用的。\n",
    "                next_seats = self.seats[row_num + 1]  # 获取下一行座位的压缩表示\n",
    "                next_seats &= ~(scheme << 1)  # 将下一行座位中与当前方案中左上方座位相邻的位置设置为不可用，即将这些位置对应的位设为 0。这是因为当前方案中左上方座位被占用了，所以下一行的这些位置不能被学生坐。\n",
    "                next_seats &= ~(scheme >> 1)  # 将下一行座位中与当前方案中右上方座位相邻的位置设置为不可用，同样将这些位置对应的位设为 0。这是因为当前方案中右上方座位被占用了，所以下一行的这些位置也不能被学生坐。\n",
    "                # 这样，经过上述操作，next_seats 中的 1 位表示下一行中可用的座位，而 0 位表示不可用的座位。在接下来的递归过程中，next_seats 将作为参数传递给 f 函数，用于计算下一行的最大学生人数。这样就确保了在计算下一行的最大学生人数时，已经考虑了当前行的座位布局。\n",
    "                ans = max(ans, curans + self.__dp(next_seats, row_num + 1, width))\n",
    "        return ans\n",
    "\n",
    "    def compress(self, row: List[str]):\n",
    "        ans = 0\n",
    "        for c in row:\n",
    "            ans <<= 1  # 与 += 相同的语法\n",
    "            if c == '.':\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        self.seats = [self.compress(row) for row in seats]\n",
    "        return self.__dp(self.seats[0], 0, len(seats[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        n = len(seats)\n",
    "        m = len(seats[0])\n",
    "        edges = [[], []]\n",
    "        s = 0\n",
    "        t = 1\n",
    "        cur = 2\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if seats[i][j] == '.':\n",
    "                    edges.append([])\n",
    "                    if j & 1 == 1: # 偶数\n",
    "                        edges[s].append(cur)\n",
    "                    else:\n",
    "                        edges[cur].append(t)\n",
    "                    seats[i][j] = cur\n",
    "                    cur += 1\n",
    "        if cur == 2: return 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if seats[i][j] != '#':\n",
    "                    cur = seats[i][j]\n",
    "                    if j + 1 < m and seats[i][j+1] != '#':\n",
    "                        if j & 1 == 1:\n",
    "                            edges[cur].append(seats[i][j+1])\n",
    "                        else:\n",
    "                            edges[seats[i][j+1]].append(cur)\n",
    "                    if i > 0:\n",
    "                        if j + 1 < m and seats[i-1][j+1] != '#':\n",
    "                            if j & 1 == 1:\n",
    "                                edges[cur].append(seats[i-1][j+1])\n",
    "                            else:\n",
    "                                edges[seats[i-1][j+1]].append(cur)\n",
    "                        if j - 1 >= 0 and seats[i-1][j-1] != '#':\n",
    "                            if j & 1 == 1:\n",
    "                                edges[cur].append(seats[i-1][j-1])\n",
    "                            else:\n",
    "                                edges[seats[i-1][j-1]].append(cur)\n",
    "        #for e in enumerate(edges): print(e)\n",
    "        #for s in seats: print(s)\n",
    "        edges2 = [[] for i in range(len(edges))]\n",
    "        for s, e in enumerate(edges):\n",
    "            if s == 0: continue\n",
    "            for i in e:\n",
    "                if i == 1: continue\n",
    "                edges2[i].append(s)\n",
    "            \n",
    "        flag = [[False] * len(edges) for _ in edges]\n",
    "        vis = [False] * len(edges)\n",
    "        p = []\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            #print(i)\n",
    "            if i == 1:\n",
    "                print('\\t', p)\n",
    "                return True\n",
    "            for j, e in enumerate(edges[i]):\n",
    "                if vis[e]: continue\n",
    "                vis[e] = True\n",
    "                if flag[i][e] == False:\n",
    "                    flag[i][e] = True\n",
    "                    p.append(e)\n",
    "                    r = dfs(e)\n",
    "                    p.pop()\n",
    "                    if r:\n",
    "                        vis[e] = False\n",
    "                        return r\n",
    "                    flag[i][e] = False\n",
    "                vis[e] = False\n",
    "            for j, e in enumerate(edges2[i]):\n",
    "                if vis[e]: continue\n",
    "                vis[e] = True\n",
    "                # print(j, i)\n",
    "                if flag[e][i] == True:\n",
    "                    flag[e][i] = False\n",
    "                    p.append(e)\n",
    "                    r = dfs(e)\n",
    "                    p.pop()\n",
    "                    if r:\n",
    "                        vis[e] = False\n",
    "                        return r\n",
    "                    flag[e][i] = True\n",
    "                vis[e] = False\n",
    "            return False\n",
    "\n",
    "        while dfs(0):\n",
    "            cur -= 1\n",
    "        return cur - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最小费用最大流，洛谷 P3381\n",
    "'''\n",
    "from collections import *\n",
    "from math import *\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val, self.v, self.next, self.w = 0, 0, 0, 0\n",
    "    def __str__(self):\n",
    "        return \"{}, {}, {}, {}\".format(self.val, self.v, self.next, self.w)\n",
    "\n",
    "class Dinic:\n",
    "    def __init__(self, src, dst, n=5010):\n",
    "        self.nodes = [Node() for _ in range(2)]\n",
    "        self.top = 1\n",
    "        self.s, self.t = src, dst\n",
    "        self.N = n\n",
    "        self.head, self.vis, self.dist = [0] * self.N, [0] * self.N, [inf] * self.N\n",
    "        self.cost, self.maxflow = 0, 0\n",
    "    \n",
    "    def _add_edge(self, u, v, val, w):\n",
    "        self.nodes.append(Node())\n",
    "        self.top += 1\n",
    "        self.nodes[self.top].v = v\n",
    "        self.nodes[self.top].w = w\n",
    "        self.nodes[self.top].val = val\n",
    "        self.nodes[self.top].next = self.head[u]\n",
    "        self.head[u] = self.top\n",
    "    \n",
    "    def add_edge(self, u, v, val, w=0):\n",
    "        self._add_edge(u , v, val, w)\n",
    "        self._add_edge(v, u, 0, -w)\n",
    "    \n",
    "    def spfa(self)->bool:\n",
    "        self.vis, self.dist = [0] * self.N, [inf] * self.N\n",
    "        self.dist[self.s], self.vis[self.s] = 0, 1\n",
    "        dq = deque([self.s])\n",
    "        \n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            self.vis[u] = 0\n",
    "            i = self.head[u]\n",
    "            while i:\n",
    "                d = self.nodes[i].v\n",
    "                if self.dist[u] + self.nodes[i].w < self.dist[d] and self.nodes[i].val:\n",
    "                    self.dist[d] = self.dist[u] + self.nodes[i].w\n",
    "                    if self.vis[d] == 0: \n",
    "                        dq.append(d)\n",
    "                        self.vis[d] = 1\n",
    "                i = self.nodes[i].next\n",
    "        return self.dist[self.t] != inf\n",
    "    \n",
    "    def dfs(self, u, flow)->int:\n",
    "        if u == self.t:\n",
    "            self.vis[self.t] = 1\n",
    "            self.maxflow += flow\n",
    "            return flow\n",
    "        used = 0\n",
    "        self.vis[u] = 1\n",
    "        i = self.head[u]\n",
    "        while i:\n",
    "            d = self.nodes[i].v\n",
    "            if (self.vis[d] == 0 or d == self.t) and self.nodes[i].val != 0 and self.dist[d] == self.dist[u] + self.nodes[i].w:\n",
    "                minflow = self.dfs(d, min(flow-used, self.nodes[i].val))\n",
    "                if minflow != 0:\n",
    "                    self.cost += self.nodes[i].w * minflow\n",
    "                    self.nodes[i].val -= minflow\n",
    "                    self.nodes[i^1].val += minflow\n",
    "                    used += minflow\n",
    "                if used == flow: break\n",
    "            i = self.nodes[i].next\n",
    "        return used\n",
    "\n",
    "    def get_max_flow_min_cost(self):\n",
    "        while self.spfa():\n",
    "            self.vis[self.t] = 1\n",
    "            while self.vis[self.t]:\n",
    "                self.vis = [0] * self.N\n",
    "                self.dfs(self.s, inf)\n",
    "        return self.maxflow, self.cost\n",
    "\n",
    "# if __name__ == '__main__':\n",
    "#     n, m, s, t = map(int, input().split())\n",
    "#     dinic = Dinic(s, t)\n",
    "#     for i in range(m):\n",
    "#         u, v, val, w = map(int, input().split())\n",
    "#         dinic.add_edge(u , v, val, w) # val->流量，w->费用\n",
    "#     ans, cost = dinic.get_max_flow_min_cost()\n",
    "#     print(ans, cost)\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        N = 100\n",
    "        src = m * N + 1\n",
    "        dst = src + 1\n",
    "        \n",
    "        dinic = Dinic(src, dst, dst+1)\n",
    "        odd, even = set(), set()\n",
    "        edges = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if seats[i][j] == '.':\n",
    "                    if j % 2 == 1: \n",
    "                        odd.add((i, j))\n",
    "                        dinic.add_edge(src, i * N + j, 1)\n",
    "                    else: \n",
    "                        even.add((i, j))\n",
    "                        dinic.add_edge(i * N + j, dst, 1)\n",
    "\n",
    "        for x, y in odd:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in even:\n",
    "                    dinic.add_edge(x * N + y, nx * N + ny,  1)\n",
    "        \n",
    "        for x, y in even:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in odd:\n",
    "                    dinic.add_edge(nx * N + ny, x * N + y, 1)\n",
    "        \n",
    "        flow, _ = dinic.get_max_flow_min_cost()\n",
    "        return len(odd) + len(even) - flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最小费用最大流，洛谷 P3381\n",
    "'''\n",
    "from collections import *\n",
    "from math import *\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val, self.v, self.next, self.w = 0, 0, 0, 0\n",
    "    def __str__(self):\n",
    "        return \"{}, {}, {}, {}\".format(self.val, self.v, self.next, self.w)\n",
    "\n",
    "class Dinic:\n",
    "    def __init__(self, src, dst, n=5010):\n",
    "        self.nodes = [Node() for _ in range(2)]\n",
    "        self.top = 1\n",
    "        self.s, self.t = src, dst\n",
    "        self.N = n\n",
    "        self.head, self.vis, self.dist = [0] * self.N, [0] * self.N, [inf] * self.N\n",
    "        self.cost, self.maxflow = 0, 0\n",
    "    \n",
    "    def _add_edge(self, u, v, val, w):\n",
    "        self.nodes.append(Node())\n",
    "        self.top += 1\n",
    "        self.nodes[self.top].v = v\n",
    "        self.nodes[self.top].w = w\n",
    "        self.nodes[self.top].val = val\n",
    "        self.nodes[self.top].next = self.head[u]\n",
    "        self.head[u] = self.top\n",
    "    \n",
    "    def add_edge(self, u, v, val, w=0):\n",
    "        self._add_edge(u , v, val, w)\n",
    "        self._add_edge(v, u, 0, -w)\n",
    "    \n",
    "    def spfa(self)->bool:\n",
    "        self.vis, self.dist = [0] * self.N, [inf] * self.N\n",
    "        self.dist[self.s], self.vis[self.s] = 0, 1\n",
    "        dq = deque([self.s])\n",
    "        \n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            self.vis[u] = 0\n",
    "            i = self.head[u]\n",
    "            while i:\n",
    "                d = self.nodes[i].v\n",
    "                if self.dist[u] + self.nodes[i].w < self.dist[d] and self.nodes[i].val:\n",
    "                    self.dist[d] = self.dist[u] + self.nodes[i].w\n",
    "                    if self.vis[d] == 0: \n",
    "                        dq.append(d)\n",
    "                        self.vis[d] = 1\n",
    "                i = self.nodes[i].next\n",
    "        return self.dist[self.t] != inf\n",
    "    \n",
    "    def dfs(self, u, flow)->int:\n",
    "        if u == self.t:\n",
    "            self.vis[self.t] = 1\n",
    "            self.maxflow += flow\n",
    "            return flow\n",
    "        used = 0\n",
    "        self.vis[u] = 1\n",
    "        i = self.head[u]\n",
    "        while i:\n",
    "            d = self.nodes[i].v\n",
    "            if (self.vis[d] == 0 or d == self.t) and self.nodes[i].val != 0 and self.dist[d] == self.dist[u] + self.nodes[i].w:\n",
    "                minflow = self.dfs(d, min(flow-used, self.nodes[i].val))\n",
    "                if minflow != 0:\n",
    "                    self.cost += self.nodes[i].w * minflow\n",
    "                    self.nodes[i].val -= minflow\n",
    "                    self.nodes[i^1].val += minflow\n",
    "                    used += minflow\n",
    "                if used == flow: break\n",
    "            i = self.nodes[i].next\n",
    "        return used\n",
    "\n",
    "    def get_max_flow_min_cost(self):\n",
    "        while self.spfa():\n",
    "            self.vis[self.t] = 1\n",
    "            while self.vis[self.t]:\n",
    "                self.vis = [0] * self.N\n",
    "                self.dfs(self.s, inf)\n",
    "        return self.maxflow, self.cost\n",
    "\n",
    "# if __name__ == '__main__':\n",
    "#     n, m, s, t = map(int, input().split())\n",
    "#     dinic = Dinic(s, t)\n",
    "#     for i in range(m):\n",
    "#         u, v, val, w = map(int, input().split())\n",
    "#         dinic.add_edge(u , v, val, w) # val->流量，w->费用\n",
    "#     ans, cost = dinic.get_max_flow_min_cost()\n",
    "#     print(ans, cost)\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        N = n\n",
    "        src = m * N + 1\n",
    "        dst = src + 1\n",
    "        \n",
    "        dinic = Dinic(src, dst, dst+1)\n",
    "        odd, even = set(), set()\n",
    "        edges = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if seats[i][j] == '.':\n",
    "                    if j % 2 == 1: \n",
    "                        odd.add((i, j))\n",
    "                        dinic.add_edge(src, i * N + j, 1)\n",
    "                    else: \n",
    "                        even.add((i, j))\n",
    "                        dinic.add_edge(i * N + j, dst, 1)\n",
    "\n",
    "        for x, y in odd:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in even:\n",
    "                    dinic.add_edge(x * N + y, nx * N + ny,  1)\n",
    "        \n",
    "        for x, y in even:\n",
    "            for dx, dy in (0, -1), (0, 1), (-1, -1), (-1, 1):\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (nx, ny) in odd:\n",
    "                    dinic.add_edge(nx * N + ny, x * N + y, 1)\n",
    "        \n",
    "        flow, _ = dinic.get_max_flow_min_cost()\n",
    "        return len(odd) + len(even) - flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        m, n, ans = len(seats), len(seats[0]), 0\n",
    "        # 确定i行座位情况下可以安排i+1行座位安排\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, seat):\n",
    "            # 枚举每行可能的座位安排情况\n",
    "            curPossibleSeats = []\n",
    "            def possibleSeats(tmp, j):\n",
    "                if j == n:\n",
    "                    curPossibleSeats.append(tmp)\n",
    "                    return \n",
    "                if seat[j] == '.': # 可以安排学生\n",
    "                    if not tmp or tmp[-1] != 'x': # 'x'表示安排了学生\n",
    "                        possibleSeats(tmp+('x',), j+1)\n",
    "                possibleSeats(tmp+(seat[j],), j+1) # 不安排学生\n",
    "            possibleSeats((), 0)\n",
    "\n",
    "            # 当前行由上一行状态决定，肯定不存在抄袭情况，所以遇到最后一行，直接返回最大安排座位数量\n",
    "            if i == m - 1:\n",
    "                return max([curSeat.count('x') for curSeat in curPossibleSeats])\n",
    "\n",
    "            ans = float('-inf')\n",
    "            for curSeat in curPossibleSeats:\n",
    "                nextSeat = seats[i+1][::]\n",
    "                cnt = 0\n",
    "                for j in range(n):\n",
    "                    if curSeat[j] == 'x': # 安排了学生\n",
    "                        cnt += 1\n",
    "                        # 左后，右后不能安排学生\n",
    "                        if j > 0:\n",
    "                            nextSeat[j-1] = '#'\n",
    "                        if j + 1 < n:\n",
    "                            nextSeat[j+1] = '#'\n",
    "                ans = max(ans, cnt + dfs(i+1, tuple(nextSeat)))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, tuple(seats[0]))\n",
    "\n",
    "    def maxStudents_error(self, seats: List[List[str]]) -> int:\n",
    "        m, n, ans = len(seats), len(seats[0]), 0\n",
    "        def checkGoodSeats(bad): # 判断是否有好的椅子\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if not bad[i][j]:\n",
    "                        return True\n",
    "            return False\n",
    "        def dfs(r, c, bad):\n",
    "            # print(f\"r:{r}, c:{c}, bad:{bad}\")\n",
    "            if not checkGoodSeats(bad):\n",
    "                return 0\n",
    "            ans = float('-inf')\n",
    "            if seats[r][c] == '.' and not bad[r][c]:\n",
    "                # print(f\"r:{r}, c:{c}\")\n",
    "                bad[r][c] = True\n",
    "                # 当前位置可以安排\n",
    "                # 将能够抄袭的位置置为坏的\n",
    "                canFlag = True\n",
    "                for diffR, diffC in [[-1, -1], [-1, 1], [0, -1], [0, 1]]:\n",
    "                    arroundR, arroundC = r + diffR, c + diffC\n",
    "                    if 0 <= arroundR < m and 0 <= arroundC < n:\n",
    "                        if not bad[arroundR][arroundC]:\n",
    "                            canFlag = False\n",
    "                            break\n",
    "                if canFlag:\n",
    "                    # 将能够抄袭的位置不能安排学生\n",
    "                    for diffR, diffC in [[-1, -1], [-1, 1], [0, -1], [0, 1]]:\n",
    "                        arroundR, arroundC = r + diffR, c + diffC\n",
    "                        if 0 <= arroundR < m and 0 <= arroundC < n:\n",
    "                            bad[arroundR][arroundC] = True\n",
    "\n",
    "                    for diffR, diffC in [[1,0], [-1, 0], [0, -1], [0, 1]]:\n",
    "                        nextR, nextC = r + diffR, c + diffC\n",
    "                        if 0 <= nextR < m and 0 <= nextC < n:\n",
    "                            ans = max(ans, 1 + dfs(nextR, nextC, bad[::][::]))\n",
    "            \n",
    "            # 当前位置不安排\n",
    "            bad[r][c] = True\n",
    "            # 遍历四周下一个位置\n",
    "            ops = [[1,0], [-1, 0], [0, -1], [0, 1]]\n",
    "            for diffR, diffC in ops:\n",
    "                nextR, nextC = r + diffR, c + diffC\n",
    "                if 0 <= nextR < m and 0 <= nextC < n:\n",
    "                    ans = max(ans, dfs(nextR, nextC, bad[::][::]))\n",
    "            return ans\n",
    "        def getBad():\n",
    "            bad = [[False] * n for _ in range(m)]\n",
    "            for r in range(m):\n",
    "                for c in range(n):\n",
    "                    if seats[r][c] == '#':\n",
    "                        bad[r][c] = True\n",
    "            return bad\n",
    "        ans = float('-inf')\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if seats[r][c] == '.':\n",
    "                    bad = getBad()\n",
    "                    ans = max(ans, dfs(r, c, bad))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "\n",
    "        m, n = len(seats), len(seats[0])\n",
    "        lst = []\n",
    "        for s in seats:\n",
    "            lst.extend(s)\n",
    "\n",
    "        k = len(lst)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state):\n",
    "            if i == k:\n",
    "                return 0\n",
    "\n",
    "            nex_state = (state - (state&1))//2\n",
    "            res = dfs(i+1, nex_state)\n",
    "            if lst[i] == \".\" and not (state & (1<<0) and i//n and i % n) and not (state&(1<<2) and i//n and i%n < n-1) and not (state & (1<<n) and i%n):\n",
    "                nex_state = (state - (state & 1)) // 2\n",
    "\n",
    "                cur = 1+dfs(i+1, nex_state |(1<<n))\n",
    "                if cur > res:\n",
    "                    res =cur\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(_, seats: List[List[str]]) -> int:\n",
    "        def cal(p, s):\n",
    "            if p % n == 0:return 1 if s[2] != '1' else 0\n",
    "            elif (p + 1) % n == 0:return 1 if s[0] != '1' and s[-1] != '1' else 0\n",
    "            else:return 1 if s[0] != '1' and s[-1] != '1' and s[2] != '1' else 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, s):\n",
    "            if p == m * n:return 0\n",
    "            else:\n",
    "                r, c = p // n, p % n\n",
    "                if seats[r][c] == '#':\n",
    "                    mx = dfs(p + 1, s[1:] + '0')\n",
    "                else:\n",
    "                    mx = max(dfs(p + 1, s[1:] + '1') + cal(p, s), dfs(p + 1, s[1:] + '0'))\n",
    "            return mx\n",
    "        m,n=len(seats),len(seats[0])\n",
    "        return dfs(0, '0' * (n+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStudents(self, seats: List[List[str]]) -> int:\n",
    "        def cal(p, s):\n",
    "            if p % n == 0:return 1 if s[2] != '1' else 0\n",
    "            elif (p + 1) % n == 0:return 1 if s[0] != '1' and s[-1] != '1' else 0\n",
    "            else:return 1 if s[0] != '1' and s[-1] != '1' and s[2] != '1' else 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, s):\n",
    "            if p == m * n:return 0\n",
    "            else:\n",
    "                r, c = p // n, p % n\n",
    "                if seats[r][c] == '#':\n",
    "                    mx = dfs(p + 1, s[1:] + '0')\n",
    "                else:\n",
    "                    mx = max(dfs(p + 1, s[1:] + '1') + cal(p, s), dfs(p + 1, s[1:] + '0'))\n",
    "            return mx\n",
    "        m,n=len(seats),len(seats[0])\n",
    "        return dfs(0, '0' * (n+1))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
